0264. 丑数 II【中等】
1. 📝 题目描述
给你一个整数 n，请你找出并返回第 n 个 丑数。
丑数 就是质因子只包含 2、3 和 5 的正整数。
示例 1：
txt
输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。1
2
3
2
3
示例 2：
txt
输入：n = 1
输出：1
解释：1 通常被视为丑数。1
2
3
2
3
提示：
1 <= n <= 1690
2. 🎯 s.1 - 三指针动态规划
c
int nthUglyNumber(int n) {
int* dp = (int*)malloc(sizeof(int) * n);
dp[0] = 1;
int p2 = 0, p3 = 0, p5 = 0;
for (int i = 1; i < n; i++) {
long a = (long)dp[p2] * 2, b = (long)dp[p3] * 3, c = (long)dp[p5] * 5;
long mn = a < b ? a : b;
mn = mn < c ? mn : c;
dp[i] = (int)mn;
if (dp[i] == a) p2++;
if (dp[i] == b) p3++;
if (dp[i] == c) p5++;
}
int res = dp[n - 1];
free(dp);
return res;
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
js
/**
* @param {number} n
* @return {number}
*/
var nthUglyNumber = function (n) {
const dp = new Array(n)
dp[0] = 1
let p2 = 0,
p3 = 0,
p5 = 0
for (let i = 1; i < n; i++) {
const a = dp[p2] * 2,
b = dp[p3] * 3,
c = dp[p5] * 5
dp[i] = Math.min(a, b, c)
if (dp[i] === a) p2++
if (dp[i] === b) p3++
if (dp[i] === c) p5++
}
return dp[n - 1]
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
py
class Solution:
def nthUglyNumber(self, n: int) -> int:
dp = [0] * n
dp[0] = 1
p2 = p3 = p5 = 0
for i in range(1, n):
a, b, c = dp[p2] * 2, dp[p3] * 3, dp[p5] * 5
dp[i] = min(a, b, c)
if dp[i] == a: p2 += 1
if dp[i] == b: p3 += 1
if dp[i] == c: p5 += 1
return dp[-1]1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
- 时间复杂度：
- 空间复杂度：
dp数组
算法思路：
- 维护三个指针 p2、p3、p5，分别表示下一个要乘 2/3/5 的丑数位置
- 每次取三者乘积的最小值作为下一个丑数，同时推进等于该值的指针